import java.util.List;

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> res;
    public List<Integer> preorder(Node root) {
        res = new ArrayList<>();
        // 递归
        //nodeRecursive(root);
        //return res;
        // 迭代
        return nodeIterator(root);
        
    }

    public void nodeIterator(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.add(node.val);
            Collections.reverse(node.children);
            for (Node item : node.children) {
                stack.add(item);
            }
        }
        return output;
    }


    public void nodeRecursive(Node root) {
        if(root == null) return;
        res.add(root.val);
        for(Node node:root.children) {
            nodeRecursive(node);
        }
    }
}